Data Structure
B tree
B Tree
A B Tree is multiway search tree having order m, m indicates how many children a node will have. B tree has following properties:
- If root is not leaf, it has at least two subtrees.
- Each intermediate node hold k - 1 keys and k references to subtrees where ceiling(m/2) <= k <=m.
- Each leaf node has k-1 keys where ceiling(m/2) <= k <=m
- All the leaves are in same level.
B Tree Node
class BTreeNode{
int m, int numberofkeys;
boolean leaf = true;
int keys[];
BTreeNode references[];
BTreeNode(int m, int n, int key){
this.m = m;
this.numberofkeys = n;
keys = new int[m-1];
references = new BTreeNode[m];
keys[0] = key;
for(int i=0;i<m;i++)
references[i] = null;
}
}
Algorithm to insert keys in B-trees:
BTreeInsert(key){
find a leaf node to insert key;
while(true){
find a proper position in found leaf node for key;
if node is have empty space{
insert key and increment numberofkeys;
return;
}else{
split node into two nodes: n1 and n2, n1 = node and n2 is new one;
distribute keys and references between n1 and n2 without violating definition of B Tree, initialize numberofkeys correctly;
key = the last key of n1;
if node is root{
create a new root node as parent of n1 and n2;
put key and references to n1 and n2 in the root, set it numberofkeys to 1;
return;
}else{
node = its parent;
}
}
}
}